package point;

/**题目：荷兰旗问题(把相同数字排在一起并进行排序)
 * y:只给定元素0，1，2的数组，要求进行排序
 * [1,0,2,0,1]->[0,0,1,1,2]
 * @Author Gavin
 * @date 2022.01.11 22:02
 */
public class solution_4 {
    /**
     * 第一种方法：分别用三个变量对数组元素进行计数，然后对
     * 数组进行填充相应的数字
     */
    //Time:O(n) Space:O(1)
    public void solution_1(int[] nums){
        if(nums==null||nums.length==0)return;
        int cnt0=0,cnt1=0,cnt2=0;
        for(int num:nums){
            if(num==0)++cnt0;
            else if(num==1)++cnt1;
            else if(num==2)++cnt2;
        }
        int k=0;
        for (int i = 0; i < cnt0; i++) nums[k++]=0;
        for (int i = 0; i < cnt1; i++) nums[k++]=1;
        for (int i = 0; i < cnt2; i++) nums[k++]=2;
    }
    /**
     * 第二种方法：使用两个游标进行处理
     * i,j分别指向首尾，mid遍历i到j之间的元素
     * 如果mid为0那么就和i进行交换，如果mid为2就和j交换
     */
    //Time:O(n) Space:O(1)
    public void solution_2(int[] nums){
        if(nums==null||nums.length==0)return;
        int left=0,mid=0,right=nums.length-1;
        while (mid<=right){
            /**
             * 这儿的疑惑点就是为什么没有处理1的情况，
             * 因为左边left指向的值肯定都是0，left当前指向的值就只能为1了，
             * mid遇到一个0就和left交换，然后left向右移动一位，这样就保证left
             * 左边全是0了，同理右边2也是这样
             */
            if(nums[mid]==0)swap(nums,left++,mid++);
            else if(nums[mid]==1)++mid;
            else swap(nums,mid,--right);
        }
    }
    private void swap(int[] nums,int i,int j){
        int tmp=nums[j];
        nums[j]=nums[i];
        nums[i]=tmp;
    }
}
